Optical navigation upon arbitrary surfaces produces motion signals indicative of relative movement along the directions of coordinate axes, and is becoming increasingly prevalent. It is used, for instance, in optical computer mice and fingertip tracking devices to replace conventional mice and trackballs for the position control of screen pointers in windowed user interfaces for computer systems. It has many advantages, among which are the lack of moving parts that accumulate dirt and suffer the mechanical wear and tear of use. Another advantage of an optical mouse is that it does not need a mouse pad, since it is generally capable of navigating upon arbitrary surfaces, so long as they are not optically featureless.
Optical navigation operates by tracking the relative displacement of images. A two dimensional view of a portion of the surface is focused upon an array of photo detectors, whose outputs are digitized and stored as a reference image in a corresponding array of memory. A brief time later a sample image is also digitized. If there has been no motion, then the sample image and the reference image are identical (or very nearly so). What is meant, of course, is that the stored arrays appear to match up. If, on the other hand, there has been some motion, then the sample image will appear to have shifted within its borders, and the digitized arrays will no longer match (that is, if their borders are also lined up). The matching process is termed xe2x80x9ccorrelationxe2x80x9d and may be performed in various ways, one of which is described in the incorporated Patents. Considered in isolation, correlation answers the narrow question xe2x80x9cAre these two images aligned?xe2x80x9d When the answer is xe2x80x9cNo,xe2x80x9d it could be because of intervening motion in any direction, and some additional mechanism is needed to find the direction and amount of displacement that will produce correlation results of xe2x80x9cYesxe2x80x9d or xe2x80x9cAlmost.xe2x80x9d What is done is to perform correlations between one of the stored images (say, the reference image) and a collection of shifted versions of the other (sample) image. The shifts are no shift, one over, one over and one up, one up, one over in the other direction, etc., for eight actual shifts and one xe2x80x9cnullxe2x80x9d shift. We would then expect that one of these nine correlations would be better than all the others, and its direction and amount of shift is taken as an indication of the intervening motion.
The navigation mechanism maintains velocity (speed and direction) information. When a new sample frame is to be correlated with the reference frame a predicted shift can be used as the starting point for the nine shifts. With this arrangement the correlation results contribute to an updated velocity and either ratify or modify the motion just predicted. Prediction is used to xe2x80x9cpre-shiftxe2x80x9d the reference frame, until such time as the new sample frame fails to overlap a significant portion of the shifted reference frame. At that time a new reference frame is taken. Prediction can be used to slow the sample rate down to conserve power (if the light source is pulsed, or can be turned off between samples) when the current velocity is low.
The basic technique described above works quite well when the surface produces images that appear as regions of light and dark defined by closed boundaries. The boundaries need not be abrupt; they can be gradual. And, if the shapes of the regions are sufficiently non-symmetrical or irregular, then any closure requirement for the boundaries can be relaxed. The shift and correlate mechanism may encounter difficulty, however, when there is a lot of symmetry and no closed boundaries. Say, for example, a mouse were navigating upon a wood grained desk. Under the right circumstances, the images presented to the correlator could appear to represent a series of parallel lines. It is easy to detect motion in the direction across the lines, but not in the direction along the lines. The result is an outfoxed mouse and a frustrated user. (Grainy surfaces are only sometimes troublesome. Much depends upon feature size, as well as orientation. Parallel features whose separation is less than the spacing between photo detectors are not resolved as separate entities. Difficult cases arise for parallel features that align with, say, every other (second) or every third photo detector. In general, the more the feature separation varies from those troublesome cases, the less difficulty arises. Just because a surface is grainy does not mean that it can produce a difficult case.)
One solution to this occasional difficulty would be to increase the resolution with which images are represented. One might magnify the image more, increase pixel density, or digitize each pixel to a greater number of bits. The hope is that eventually what appears to be regular repeating (and thus indistinguishable) features become irregular (and thus distinguishable from one another). Each of these solutions has its own disadvantage, among which are increased cost and complexity, and a need for greater speed just to maintain a given rate of tracking over the surface.
Another technique that has been used to mitigate the parallel line problem is (spatial) filtering the images before they are correlated. The idea is to modify the arrays to be correlated such that a regular pattern in the data is suppressed, at least in part. This allows the response of the correlation mechanism to be based more on irregular features in the image and less on regular recurring features that produce strong correlations not dependent upon motion. The idea is similar to filtering out a known strong signal to recover a weaker one. The filtering is performed by altering the values in the various positions of an array according to arithmetic combination with the values in symmetrically opposed positions disposed around the location of interest. The removal of an interfering signal by common mode rejection with a differential amplifier comes to mind. An example will be given in due course, but even at present it will be suspected that this technique distorts or alters the image being tracked. This is acceptable, since we are not particularly interested in such fidelity, anyway. We are never going to display to anyone the contents of the array as an image; we simply want to track it. The prior art contains different spatial filters usable in the manner we have just described, and once a suitable one has been identified by the designer it is simply incorporated as a permanent feature into the system.
One such (spatial) filter has been used in conventional optical mice to deal with the problem of parallel lines arising from, say, wood grain. It is effective in two orthogonal directions (relative to the spatial pattern with which the array of photo sensors is laid out), and we shall call it the xe2x80x9cStandardxe2x80x9d filter. There is, however, a substantial range of orientations midway between these two axes that fool the Standard filter, and at which the mouse again begins to appear confused if it encounters long parallel features. What to do?
A solution to the problem of optically navigating upon grainy surfaces whose orientation is inclined at about 45xc2x0 to the X and Y axes of the navigation mechanism is to: First, detect that the spatial filter in use is inappropriate for the orientation presently occurring, and; Second, employ a different and more appropriate spatial filter subsequent to such detection. Two additional filters have been developed that are respectively effective about the 45xc2x0 and 135xc2x0 inclinations (the trouble regions) of the Standard filter (which is oriented along the X and Y axes). A test has been developed for the shape of a correlation surface (or bowl, if viewed from underneath) used in the navigation process. The test uses the presence of a transverse ridge (or saddle) in the correlation surface (bowl), and generates control metrics whose excursions are tracked by a control system that changes the filter in use. The control system incorporates a time constant to prevent thrashing and excessive sensitivity to isolated random variations. The direction from which illumination arrives relative to the X and Y axes appears to have an effect on the range of angles (relative to, say, the Y axis) that a filter is effective, by changing the apparent size and proportions of the highlights and shadows that are the perceived features ultimately navigated upon. For example, if light strikes the navigation surface as rays essentially parallel to the Y axis (a common practice) then the angular range of operation (for grain orientation) of the Standard filter about the X axis may be about half the corresponding range about the Y axis. Similar asymmetries in the ranges of operation are noticed in the inclined filters. The operation of the control system can be enhanced by ensuring overlap of the ranges of filter operation, lest lack of overlap induce control system instability. Filter range overlap can be promoted by dynamically altering the direction from which illumination reaches the navigation surface so that it corresponds to, or varies in relation with, the filter in use.